package mao.leetcode.others.leetcode109;

public class Solution {
//    public TreeNode sortedListToBST(ListNode head) {
//        ArrayList<Integer> arr = new ArrayList<>();
//        while (head != null){
//            arr.add(head.val);
//            head=head.next;
//        }
//        return sortedArrayToBST_helper(arr,0,arr.size()-1);
//    }
//
//    public TreeNode sortedArrayToBST_helper(List<Integer> list, int start, int end) {
//        if (start > end) return null;
//        if (start == end) return new  TreeNode(list.get(start));
//        int mid = start+(end-start)/2;
//        TreeNode root = new TreeNode(list.get(mid));
//        root.left=sortedArrayToBST_helper(list,start,mid-1);
//        root.right=sortedArrayToBST_helper(list,mid+1,end);
//        return root;
//    }

    public TreeNode sortedListToBST(ListNode head) {
        return sortedListToBST_helper(head,null); //最后一个不处理的节点为null
    }

    public TreeNode sortedListToBST_helper(ListNode head,ListNode tail) {
        if (head == tail) return null;
        if (head.next == tail) return new TreeNode(head.val); //这句其实也可以由上面一句在下一次递归时生效
        ListNode fast = head; //fast  不用精确指向末尾指针，只需要mid即可。
        ListNode slow = head;
        while (fast != tail && fast.next != tail){
            slow = slow.next;
            fast=fast.next.next;
        }
        TreeNode mid = new TreeNode(slow.val);
        mid.left=sortedListToBST_helper(head,slow);
        mid.right=sortedListToBST_helper(slow.next,tail);
        return mid;
    }


    public class TreeNode {
        int val;
        Solution.TreeNode left;
        Solution.TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }

}
